package leetcode.stack_queue;

import java.util.PriorityQueue;

public class MedianFinder {

    PriorityQueue<Integer> pq1;//保存较大一半的数字，个数为奇数时少一个
    PriorityQueue<Integer> pq2;//保存较小的一半，个数为奇数时多一个

    public MedianFinder() {
        pq1 = new PriorityQueue<>();//保存较大一半的数字，个数为奇数时少一个 小根堆
        pq2 = new PriorityQueue<>((o1, o2) -> o2 - o1);//保存较小的一半，个数为奇数时多一个   大根堆
    }

    public void addNum(int num) {
        pq1.offer(num);
        pq2.offer(pq1.poll());
        if (pq2.size() - 1 > pq1.size())
            pq1.offer(pq2.poll()); //把最大的上供个pq1
    }
    public double findMedian() {
        if (pq1.size() == pq2.size()) return (pq1.peek() + pq2.peek()) / 2.0;
        return pq2.peek();
    }


    public static void main(String[] args) {


        PriorityQueue<Integer> objects = new PriorityQueue<>((o1, o2) -> o2 - o1);
        objects.offer(13);
        objects.offer(30);
        objects.offer(3);
        objects.offer(2);
        objects.offer(14);
        System.out.println(objects.poll());
        System.out.println(objects.poll());
        System.out.println(objects.poll());
        System.out.println(objects.poll());
        System.out.println(objects.poll());

    }
}
